package com.bruce.algorithm.sort;


import java.util.Arrays;

/**
 * 归并排序
 * <br>CreateDate  2021/11/03 15:01:51
 *
 * @author luotuan
 * @version 1.0.0
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] array = {1,3,2,6,8,10,20,11,9};
        sort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }

    public static void sort(int[] a,int left,int right){
        if(left==right){
            return;
        }
        int mid = left + ((right - left) >> 1);
        sort(a,left,mid);
        sort(a,mid+1,right);
        merge(a,left,mid,right);
    }

    private static void merge(int[] a,int left,int mid,int right){
        // 临时数组
        int[] tmp = new int[right-left+1];
        int index = 0;
        int leftPoint = left;
        int rightPoint = mid+1;
        // 合并2个已归并的数组
        while (leftPoint<=mid && rightPoint<=right){
            tmp[index++] = a[leftPoint]>a[rightPoint]?a[rightPoint++]:a[leftPoint++];
        }
        // 上面2个指针肯定有1个会走完
        while (leftPoint<=mid){
            tmp[index++] = a[leftPoint++];
        }
        while(rightPoint<=right){
            tmp[index++] = a[rightPoint++];
        }
        // 把临时数据数据复制到原数组
        for(int i=0;i<tmp.length;i++){
            a[left+i] = tmp[i];
        }
    }
}
